1. Field of the Invention
The present invention relates to a method and apparatus for generating and displaying freeform strokes and, more specifically, to a method and apparatus for generating and displaying points along a centerline curve and right and left offset curves of a freeform stroke, wherein the width of the centerline curve varies in the same parameter as the horizontal and vertical coordinates of the centerline curve.
2. Description of the Related Art
Freeform curves have useful applications in, for example, computer aided design and manufacturing systems, computer graphics, graphic arts, and typesetting for creating both uniform and variable-width curves. Furthermore, various methods and apparatus exist for presenting graphical representations of such freeform curves. For example, U.S. Pat. No. 4,933,889 issued to Meshkat et al. discloses a method for generating finite elements for representing the shape of an object.
In particular, spline curves have been studied extensively, and are in general use in computer graphics (see generally, Bartels, R. H. et al., An Introduction to Splines for Use in Computer Graphics and Geometric Modeling, Morgan Kauffman Publishers, Los Altos, Calif., 1987; Farin, G., Curves and Surfaces for Computer Aided Geometric Design, Academic Press, San Diego, Calif., 1988).
Spline curves have also been used in computer graphics to generate and display freeform strokes of both constant and varying width in addition to curves, which have no width. For example, Chua, Y. S., Bezier Brushstrokes, Computer-Aided Design, Butterworth-Heinemann, Vol. 22, No. 9 (November 1990), pp. 550-55, 604 ("the Chua article"), discloses a technique for using Bezier curves to mathematically model brushstrokes. The Chua article teaches using Bezier functions to model various attributes of a brushstroke, e.g., variations of shape or outline of the brushstroke, shade or color variation along and across the brushstroke, and some effects due to the variation of moisture content of the brush as well as paper characteristics. The Chua article defines a brushstroke by at least one brush segment, the shape (or outline) of which is modeled with two cubic Bezier curves (called "Bezier segments"). Each Bezier segment is associated with a parameter u, called the "parameter along the brush segment," with u=0 at the beginnings of the segments and u=1 at the ends of the segments. The shape of a general brushstroke can be modeled using one or more brush segments.
As another example, U.S. Pat. No. 4,912,659 issued to Liang et al. discloses a pipeline and parallel processing system for generating surface patches for both wireframe and solid/shaded models in a raster graphics display, wherein the inputs to a transformation processor are the parameters for a rational Bezier surface.
Offset curves have also received considerable attention, primarily in the CAD community (see generally, Farin, G., Curvature Continuity and Offsets for Piecewise Conics, TOG 8, 2 (April 1989), pp. 89-99; Farouki, R., and Neff, C., Algebraic Properties of Plane Offset Curves, CAGD, p. 297-299; Farouki, R., and Neff, C., Analytic Properties of Plane Offset Curves, CAGD, pp 297-299; Hoschek, J., Spline Approximation of Offset Curves, CAGD 5 (1988), pp. 33-40; Klass, R., An Offset Spline Approximation for Plane Curves, CAD 15, 5 (September 1983), pp. 297-299). Various definitions of offset curves exist. The predominant definition, however, is one based on a centerline or "generator" curve with an offset a distance w defined along a unit normal to each point of the centerline curve. In the absence of a sign convention for the unit normal, an offset curve is defined on both sides of the centerline curve. Generally, the term "left offset curve" designates the offset curve based upon a unit normal given by a positive sign, while the term "right offset curve" designates the offset curve based upon a unit normal by the negative sign. Further, the term "offset curve" is used to refer to one or the other of the left and right offset curves, while the term "offset curve pair" indicates both the left and right offset curves.
While the increased generality of offset curves makes them a more powerful means of expressing curves and surfaces as compared to other conventional techniques, their use has generally been restricted to applications for which they are natural. For example, offset surfaces are used to describe tolerance zones (see, e.g., Hoschek, J., Spline Approximation of Offset Curves, CAGD 5 (1988), pp. 33-40), outside surfaces of materials for which the inner surface is the reference (see, e.g., Hoschek, J., Spline Approximation of Offset Curves, CAGD 5 (1988), pp. 33-40; Klass, R., An Offset Spline Approximation for Plane Curves, CAD 15, 5 (September 1983), pp. 297-299), and machine-tool paths (see, e.g., Farouki, R., and Neff, C., Analytic Properties of Plane Offset Curves, CAGD, pp. 297-299).
The majority of applications of offset curves are motivated by physical problems involving constant width offset curves. Because constant width offset curves of spline curves are not spline curves (they are generally non-algebraic), most attention has been given to the efficient approximation of offsets with algebraic (usually rational or non-rational spline) curves. More generally, however, offset curves may have variable widths.
For example, U.S. Pat. No. 4,620,287 issued to Yam ("Yam") discloses a method and apparatus for representing uniform width curves, i.e., strokes having uniform widths. In particular, Yam discloses a technique wherein a curve is approximated by a series of Bezier curves. Each Bezier curve is provided with a predetermined width defined by a corresponding rectangle having the predetermined width. The ends of each of the rectangles are smoothed and rounded so that adjacent rectangles approximate a curve having a constant width.
As another example, Pham, B., Expressive Brushstrokes, CVGIP: Graphical Models and Image Processing, Vol. 53, No. 1 (January 1991), pp. 1-6 ("the Pham article"), discloses a technique for modeling brush strokes based on variable offset approximations of uniform cubic B-splines. An operator specifies a set of points, or knots, on a curve representing a brush stroke. Using an inversion algorithm, control vertices of a cubic B-spline are obtained to construct a cubic B-spline through the knots. Next, given an offset distance for each of the knots of the original curve, corresponding offset knots are obtained. The offset distances are measured from the corresponding knot of the original curve in a direction normal to the curve. Finally, using the inversion algorithm, offset control vertices are obtained from the offset knots to construct an offset cubic B-spline curve through the offset knots.